package com.yang.StackAndQueue;

import java.util.Deque;
import java.util.LinkedList;

public class LeetCode20 {
    public static void main(String[] args) {

    }

}

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new LinkedList();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            // 根据对应的左括号加入右括号
            if(ch == '{')stack.push('}');
            else if (ch == '(')stack.push(')');
            else if (ch == '[')stack.push(']');
                // 如果不执行上面 说明开始收尾括号或者说括号的顺序开始不对了
                // 所以如果栈为空，字符串却还没循环结束，说明括号对不上  或者直接对比不相同
            else if (stack.isEmpty() || ch!=stack.peek()) return false;
                // 如果都不是 那就是栈顶和字符串尾相等 就是括号对的上 那就移除
            else stack.pop();
        }
        // 如果字符串结束 栈也为空，那就说明匹配正确
        return stack.isEmpty();
    }
}
